package AlgorithmDesignAndAnalysis.DynamicProgamming;

public class KnapSack {
    private int NUM  = 50;
    private int CAP = 1500;
    private int[] weight = new int[NUM];
    private int[] value = new int[NUM];
    private int[][] p = new int[NUM + 1][CAP + 1];

    public void knapsack(int n, int w) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < w; j++) {
                if (j < weight[i]) {
                    p[i+1][j] = p[i + 1][j];
                } else {
                    p[i + 1][j] = Math.max(p[i][j], p[i][j - weight[i]] + value[i]);
                }
            }
        }
    }
}
